package suanfa;

import java.util.ArrayList;
import java.util.List;



public class widthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode,Integer>> q=new ArrayList<>();//数组模拟队列
        q.add(new Pair<TreeNode ,Integer>(root,1));
        int ret=0;//记录最终的结果
        while(!q.isEmpty()){
            //先更新这一层的宽度
            Pair<TreeNode,Integer> t1=q.get(0);
            Pair<TreeNode,Integer> t2=q.get(q.size()-1);
            ret=Math.max(ret,t2.getValue()-t1.getValue()+1);
            //让下一层进列
            List<Pair<TreeNode,Integer>> tmp=new ArrayList<>();
            for(Pair<TreeNode,Integer> t:q){
                TreeNode node=t.getKey();
                int index=t.getValue();
                if(node.left!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.left,index*2));
                }
                if(node.right!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.right,index*2+1));
                }
            }
            q=tmp;
        }
        return ret;
    }
}
